﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Task_16_generator
{
	class GraphNode
	{
		public int Value;
		public bool isVisited;
		List<GraphNode> previous;
		List<GraphNode> next;

		public List<GraphNode> Previous
		{
			get
			{
				if (previous == null)
				{
					previous = new List<GraphNode>();
				}
				return previous;
			}

            set { previous = value; }
		}

		public List<GraphNode> Next
		{
			get
			{
				if (next == null)
				{
					next = new List<GraphNode>();
				}
				return next;
			}

            set { next = value; }
		}

		public GraphNode(int value)
		{
			Value = value;
		}
	}

	class Program
	{
		static void Main(string[] args)
		{
		    //int n = int.Parse(Console.ReadLine());

            Dictionary<int, GraphNode> graph = new Dictionary<int, GraphNode>();

			Random rnd = new Random();
			int n = 2500;
			for (int i = 0; i < n; i++)
			{
				//string input = Console.ReadLine();
				//string[] inputArr = input.Split(' ');
				//int first = int.Parse(inputArr[0]);
				//int second = int.Parse(inputArr[1]);

				int first = rnd.Next(0, n);
				int second = rnd.Next(0, n);

				if (!graph.ContainsKey(first))
				{
					graph.Add(first, new GraphNode(first));
				}
				if (!graph.ContainsKey(second))
				{
					graph.Add(second, new GraphNode(second));
				}

				GraphNode node;
				GraphNode depend;

				graph.TryGetValue(second, out node);
				graph.TryGetValue(first, out depend);

				node.Previous.Add(depend);
				depend.Next.Add(node);
			}

			var nodes = from p in graph.Values where p.Previous.Count == 0 select p;
			if (nodes.Count() == 0)
			{
				Console.WriteLine("Not valid");
				return;
			}

			Queue<GraphNode> toVisit = new Queue<GraphNode>();

			foreach (GraphNode tempNode in nodes)
			{
				toVisit.Enqueue(tempNode);
			}
			int visitedCount = 0;

			List<int> result = new List<int>();
			while (toVisit.Count > 0)
			{
				GraphNode currentNode = toVisit.Dequeue();
				bool previousVisited = (from p in currentNode.Previous where p.isVisited == false select p).Count() == 0;
				if (currentNode.Previous.Count == 0 || previousVisited)
				{
					if (!currentNode.isVisited)
					{
						result.Add(currentNode.Value);
						visitedCount++;
					}

					currentNode.isVisited = true;
					foreach (GraphNode tempNode in currentNode.Next)
					{
						toVisit.Enqueue(tempNode);
					}
				}
			}

            //if (visitedCount < graph.Count())
            //{
                List<GraphNode> lstNodes = (from p in graph.Values select p).ToList();
                ConvertToMatrixAndPrint(lstNodes, n);
                //int counter = 0;
                //foreach (GraphNode node in lstNodes)
                //{
                //    foreach (GraphNode prevNode in node.Previous)
                //    {
                //        Console.WriteLine("{0} {1}", prevNode.Value, node.Value);
                //        counter++;
                //    }
                //}
                //Console.WriteLine(counter);
			//}
            //else
            //{
            //    //for (int i = 0; i < result.Count; i++)
            //    //{
            //    //    if (i < result.Count - 1)
            //    //    {
            //    //        Console.Write("{0}, ", result[i]);
            //    //    }
            //    //    else
            //    //    {
            //    //        Console.WriteLine(result[i]);
            //    //    }
            //    //}
            //    List<GraphNode> lstNodes = (from p in graph.Values select p).ToList();
            //    int counter = 0;
            //    foreach (GraphNode node in lstNodes)
            //    {
            //        foreach (GraphNode prevNode in node.Previous)
            //        {
            //            Console.WriteLine("{0} {1}", prevNode.Value, node.Value);
            //            counter++;
            //        }
            //    }
            //    Console.WriteLine(counter);
            //}
		}

        static void ConvertToMatrixAndPrint(List<GraphNode> lstNodes, int nodesCount)
        {
            lstNodes.First().Previous.Add(lstNodes.Last());
            lstNodes.Last().Next.Add(lstNodes.First());
            int[,] graph = new int[nodesCount, nodesCount];
            //int counter = 0;
            foreach (GraphNode node in lstNodes)
            {
                foreach (GraphNode prevNode in node.Previous)
                {
                    if (prevNode.Value != node.Value)
                    {
                        graph[prevNode.Value, node.Value] = 1;
                        graph[node.Value, prevNode.Value] = 1;
                    }
                    //Console.WriteLine("{0} {1}", prevNode.Value, node.Value);
                    //counter++;
                }
            }

            StringBuilder graphMatrix = new StringBuilder();
            graphMatrix.AppendLine(nodesCount.ToString());

            for (int i = 0; i < nodesCount; i++)
            {
                for (int j = 0; j < nodesCount; j++)
                {
                    graphMatrix.AppendFormat("{0}, ", graph[i, j]);
                }
                graphMatrix.Remove(graphMatrix.Length - 2, 1);
                graphMatrix.AppendLine();
            }

            Console.Write(graphMatrix.ToString());
        }
	}
}
